/*Copyright (C) 2013-2021 LZE*/
#include<bits/stdc++.h>
#define INF 0x7fffffff
#define mod 1000000007
#define eps 1e-6
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
const int N=1000010;
const int M=100010;
ll exgcd(ll a,ll b,ll &x,ll &y){
    if(!b){
        x = 1; y = 0;
        return a;
    }
    ll ret = exgcd(b,a % b,x,y);
    ll t = x;
    x = y;
    y = t - a / b * y;
    return ret;
}
int main() {
    ll a,b;
	scanf("%lld%lld",&a,&b);
    ll x,y;
    exgcd(a,b,x,y);
    printf("%lld\n",(x % b + b) % b);
	return 0;
}
